
#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// 75. Sort Colors
// https://leetcode.com/problems/sort-colors/description/
//
// 三路快速排序的思想
// 对整个数组只遍历了一遍
// 时间复杂度: O(n)
// 空间复杂度: O(1)
class Solution
{
public:
    void sortColors(vector<int> &nums)
    {
        int zero = -1;         // [0...zero]的索引全部存0，所以初始的时候，设置一个无效索引
        int two = nums.size(); //[two...n-1]的索引全部存2，所以初始的时候，设置一个无效索引
        // 遍历vector
        // 注意这里，不要i++,因为++是有条件的
        // 同时，这里终止条件是i<two
        for (int i = 0; i < two;)
        {
            if (nums[i] == 1)
                i++;
            else if (nums[i] == 2)
                // 把2移到索引two的位置
                swap(nums[i], nums[--two]);
            else
            {
                // nums[i]==0
                assert(nums[i] == 0); // 防止输入错误
                // 把0移动到索引zero的位置
                zero++;
                swap(nums[zero], nums[i]);
                i++;
                // swap(nums[++zero], nums[i++]);
            }
        }
    }
};

int main()
{
    int nums[] = {2, 2, 2, 1, 1, 0};
    vector<int> vec = vector<int>(nums, nums + sizeof(nums) / sizeof(int));

    Solution().sortColors(vec);
    for (int i = 0; i < vec.size(); i++)
        cout << vec[i] << " ";
    cout << endl;
}